package com.cty._05_Ability._59_02_QueueWithMax;

import java.util.LinkedList;

/**
 * @Auther: cty
 * @Date: 2020/7/24 16:45
 * @Description: 面试题59（二）：队列的最大值
 * 题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，
 * 如果输入数组{2, 3, 4, 2, 6, 2, 5, 1}及滑动窗口的大小3，那么一共存在6个
 * 滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}。
 * @version: 1.0
 */
public class QueueWithMax {
    private LinkedList<Integer> dataQueue;
    private LinkedList<Integer> maxQueue;

    public QueueWithMax(){
        dataQueue = new LinkedList<>();
        maxQueue = new LinkedList<>();
    }

    public void push_back(int number){
        while(!maxQueue.isEmpty() && number>=maxQueue.peekLast())
            maxQueue.removeLast();

        maxQueue.addLast(number);
        dataQueue.addLast(number);
    }

    public int pop_front() throws Exception {
        if(dataQueue.isEmpty())
            throw new Exception("queue is empty");

        int front = dataQueue.removeFirst();
        if(!maxQueue.isEmpty() && maxQueue.peekFirst() == front)
            maxQueue.removeFirst();
        return front;
    }

    public int max() throws Exception {
        if(maxQueue.isEmpty())
            throw new Exception("queue is empty");

        return maxQueue.peekFirst();
    }
}  // end class
